/**
 * @version Create on 2012-11-13
 * @author Yinzi Chen
 */

public class UniqueBinarySearchTrees {

	public int numTrees(int n) {
		int[] d = new int[n + 1];
		d[0] = 1;
		d[1] = 1;
		for (int i = 2; i <= n; ++i) {
			for (int j = 0; j < i; ++j) {
				d[i] += d[j] * d[i - j - 1];
			}
		}
		return d[n];
	}

	public static void main(String[] args) {
		UniqueBinarySearchTrees a = new UniqueBinarySearchTrees();
		System.out.println(a.numTrees(3));
	}

}
